package array;

import java.util.HashMap;
import java.util.Map;

public class LongestConsecutiveSequence128 {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n: nums) {
            map.put(n, 1);
        }

        for (int n: nums) {
            // 这里很关键, 避免重复遍历
            if (!map.containsKey(n-1)) {
                int m = n + 1;
                while (map.containsKey(m)) {
                    map.put(m, m - n + 1);
                    m++;
                }
            }
        }

        int maxLen = 0;
        for (int n: nums) {
            maxLen = Math.max(maxLen, map.get(n));
        }

        return maxLen;
    }
}
